package top.humbleyuan.dp;

/**
 * @Author: yuanhuanghui
 * @Date: 2020-08-05
 * @Time: 15:57
 * @Description: 最长回文子串
 * @pro: 待补充中心扩展方法
 */
public class LeetCode_5 {
    /**
     * dp[i][j]存储串s从i到j是否是回文串
     * 1. 初始化dp，单个字符是回文串
     * 2. 递推：
     * s[i] == s[j] && (dp[i + 1][j - 1] || j - i == 1) => dp[i][j] = true
     * 注意dp构造顺序从后面开始
     */
    public static void main(String[] args) {
        String s = "abba";

        if(s == null || s.length() == 0) {
            System.out.println("");
        }
        // dp
        boolean[][] dp = new boolean[s.length()][s.length()];

        for(int i = 0;i < s.length(); i++) {
            dp[i][i] = true;
        }

        int maxLen = 0;
        String res = s.charAt(0) + "";
        for(int i = s.length() - 1;i >= 0;i--) {
            for(int j = i + 1; j < s.length();j++) {
                // 这里要分情况
                if((s.charAt(i) == s.charAt(j)) && (dp[i + 1][j - 1] || j - i == 1)) {
                    dp[i][j] = true;
                    if(j - i > maxLen) {
                        maxLen = j - i;
                        res = s.substring(i, j + 1);
                    }
                }
            }
        }

        System.out.println(res);

    }
}
